//
// Created by daiyizheng on 2022/4/12.
//

#include <vector>
#include <algorithm>
using namespace std;
//最长递增子数组（连续）, 递增子序列（不连续）
class Solution {
public:
    //最长递增子数组（连续）
    //nums[i]>nums[i-1] dp[i] = dp[i-1] +1
    //nums[i]<=nums[i-1] dp[i]=1
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size()==0)return 0;
        int n = nums.size();
        vector<int> dp(n, 1);
        //不用初始化
        int maxLen  = 1;
        for (int i = 1; i < n; i++) {
            if(nums[i]>nums[i-1]){
                dp[i] = dp[i-1]+1;
                maxLen = max(dp[i], maxLen);
            }
        }
        return maxLen;
    }
    //递增子序列（不连续）nums[j]>nums[i]  dp[j] = max(dp[i]+1, dp[j])
    //                nums[j]<=nums[i-1] dp[j]=1
    int lengthOfLIS1(vector<int>& nums) {
        if (nums.size()==0)return 0;
        int n = nums.size();
        vector<int> dp(n, 1);
        int maxLen  = 1;

        for (int j = 1; j < n; ++j) {
            for (int i = 0; i < j; ++i) {
                if (nums[j]>nums[i]){
                    dp[j] = max(dp[i]+1, dp[j]);
                    maxLen = max(dp[j], maxLen);
                }
            }
        }
        return maxLen;
    }
};


